//42.接雨水
//https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public:
    int trap(vector<int>& height) {
        //从前往后计算 前i个柱子中的最高柱子
        //再从后往前计算 后i个柱子中最高的柱子
        int n = height.size();
        vector<int> v1(n),v2(n);
        //初始化下 从前往后初始化height[0] 从后往前初始化height[n-1]
        v1[0] = height[0];
        v2[n-1] = height[n-1];
        //分别记录左边v1和右边v2最高和最高的柱子
        for(int i = 1;i<n;++i)
        {
            v1[i] = max(v1[i-1],height[i]);
            v2[n-i-1] = max(v2[n-i],height[n-i-1]);
        }

        int ret = 0;
        //由于木桶原理 能接水的由最低柱子决定 减去当前的高度就是节水量
        for(int i = 0;i<n;++i)
            ret += min(v1[i],v2[i])-height[i];
        return ret;
    }
};